package agent;
import instanceXMLParser.Instance;

import java.util.ArrayList;
import java.util.List;

import org.jgrapht.DirectedGraph;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.alg.FloydWarshallShortestPaths;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

import aima.core.agent.Action;
import aima.core.agent.impl.DynamicAction;
import aima.core.agent.impl.NoOpAction;

import com.google.common.collect.Collections2;

import core.VacuumEnvironment.LocationState;

//row major enumeration of edges
public class Vacuum_Agent_Solver extends AbstractVacuumSolver implements Runnable{


	UndirectedGraph<Integer, DefaultEdge> board;
	Instance instance;
	List<Integer> targetCells = new ArrayList<Integer>();

	//int[][]distancesMatrix;

	final int INFDIST=1000000;
	final int LIMIT_TARG_OPT=12;



	List<ArrayList<Integer>> powerSet = new ArrayList<ArrayList<Integer>>();


	int bestNumCleaned=Integer.MIN_VALUE;
	double bestCost=Integer.MAX_VALUE;

	List<Integer> bestPermutation = new ArrayList<Integer>();
	List<Integer> completeSolutionPath;

	//FloydWarshallShortestPaths<Integer, DefaultEdge> shortesTpath;


	List<Action> solution;

	int [][] distances;

	public Vacuum_Agent_Solver() {
		id="perfect";
	}

	//	private int shortestDistance(Integer int0, Integer int1){
	//		Integer res=(int)shortesTpath.shortestDistance(int0, int1);
	//		if(res< INFDIST){
	//			return res;
	//		}else{
	//			return INFDIST;
	//		}
	//	}

	private int shortestDistance(Integer i, Integer j) {
		if(i==j){
			return 0;
		}

		Integer res = distances[i][j];
		if(res==-1){
			List<DefaultEdge> path=DijkstraShortestPath.findPathBetween(board, i, j);
			if(path==null){
				distances[i][j]=INFDIST;
			}else{
				distances[i][j]=path.size();
			}
		}
		return distances[i][j];

	}


	public String getId(){
		return id;
	}

	public void solve(){
		long startTime = System.currentTimeMillis();

		//		instance.toString();

		//distancesMatrix = new int[instance.getSize()*instance.getSize()][instance.getSize()*instance.getSize()];
		board= createGraph();

		distances= new int [instance.getSize()*instance.getSize()][instance.getSize()*instance.getSize()];
		for (int i = 0; i < instance.getSize()*instance.getSize(); i++) {
			for (int j= 0; j < instance.getSize()*instance.getSize(); j++) {
				distances[i][j]=-1;
			}
		}

		//shortesTpath = new FloydWarshallShortestPaths<Integer, DefaultEdge>(board);
		//System.out.println(shortestDistance(0, 7)+"distanza zero sette");
		//calculateDistancesFloys();
		targetCells=listAllreachableTarget();
		if(targetCells.size() <= LIMIT_TARG_OPT){
			//System.out.println(targetCells);
			calculatePowerSet();

			isSolvable();
			calculateBestSolution();

			completeSolutionPath=buildCompletePath();


			//validate cost
			//System.out.println();
			List<Integer> visited=new ArrayList<>();
			int cost=0;
			for (int sol = 0; sol < completeSolutionPath.size()-1; sol++) {
				if(targetCells.contains(completeSolutionPath.get(sol)) && !visited.contains(completeSolutionPath.get(sol)) && bestPermutation.contains(completeSolutionPath.get(sol))){
					cost+=1;//suck operation
					visited.add(completeSolutionPath.get(sol));
				}
				cost+=shortestDistance(completeSolutionPath.get(sol), completeSolutionPath.get(sol+1));
			}
			//System.out.println("costo soluzione = "+completeSolutionPath+" ="+cost);
			//System.out.println("cost = "+(completeSolutionPath.size()-1+bestPermutation.size()));


			solution= new ArrayList<Action>(completeSolutionPath.size()+bestPermutation.size());
			buildSolutionFromVertexPath();

			long estimatedTime = System.currentTimeMillis() - startTime;

			//System.out.println("\nelapsed time "+ (double)(estimatedTime)/1000+" seconds");
		}else{
			solution = null;
			//System.out.println("Optimal Solution not computable! The problme is NP-Complete m8");
		}

	}

	public void solve(String path){
		long startTime = System.currentTimeMillis();


		instance = new Instance();
		instance.buildINstanceJDom(path);


		//		instance.toString();

		//distancesMatrix = new int[instance.getSize()*instance.getSize()][instance.getSize()*instance.getSize()];
		board= createGraph();

		//shortesTpath = new FloydWarshallShortestPaths<Integer, DefaultEdge>(board);
		//System.out.println(shortestDistance(0, 7)+"distanza zero sette");
		//calculateDistancesFloys();
		targetCells=listAllreachableTarget();
		if(targetCells.size() <= LIMIT_TARG_OPT){
			//System.out.println(targetCells);
			calculatePowerSet();

			isSolvable();
			calculateBestSolution();

			completeSolutionPath=buildCompletePath();


			//validate cost
			//System.out.println();
			List<Integer> visited=new ArrayList<>();
			int cost=0;
			for (int sol = 0; sol < completeSolutionPath.size()-1; sol++) {
				if(targetCells.contains(completeSolutionPath.get(sol)) && !visited.contains(completeSolutionPath.get(sol)) && bestPermutation.contains(completeSolutionPath.get(sol))){
					cost+=1;//suck operation
					visited.add(completeSolutionPath.get(sol));
				}
				cost+=shortestDistance(completeSolutionPath.get(sol), completeSolutionPath.get(sol+1));
			}
			//System.out.println("costo soluzione = "+completeSolutionPath+" ="+cost);
			//System.out.println("cost = "+(completeSolutionPath.size()-1+bestPermutation.size()));


			solution= new ArrayList<Action>(completeSolutionPath.size()+bestPermutation.size());
			buildSolutionFromVertexPath();

			long estimatedTime = System.currentTimeMillis() - startTime;

			//System.out.println("\nelapsed time "+ (double)(estimatedTime)/1000+" seconds");
		}else{
			solution = null;
			//System.out.println("Optimal Solution not computable! The problme is NP-Complete m8");
		}

	}



	public void solveFromInstance(Instance i ){
		long startTime = System.currentTimeMillis();

		instance=i;
		//		instance.toString();

		//distancesMatrix = new int[instance.getSize()*instance.getSize()][instance.getSize()*instance.getSize()];
		board= createGraph();

		//shortesTpath = new FloydWarshallShortestPaths<Integer, DefaultEdge>(board);

		//calculateDistancesFloys();
		targetCells=listAllreachableTarget();

		if(targetCells.size() <= LIMIT_TARG_OPT){
			calculatePowerSet();

			isSolvable();
			calculateBestSolution();

			completeSolutionPath=buildCompletePath();


			//validate cost
			int cost=0;
			cost+=bestPermutation.size()-2;
			for (int sol = 0; sol < completeSolutionPath.size()-1; sol++) {
				cost+=shortestDistance(completeSolutionPath.get(sol), completeSolutionPath.get(sol+1));
			}
			cost+=shortestDistance(completeSolutionPath.get(completeSolutionPath.size()-1), RowMajIdx(instance.getBasePos().getX(), instance.getBasePos().getY(), instance.getSize()));
			//System.out.println("costo soluzione = "+completeSolutionPath+" ="+cost);


			solution= new ArrayList<Action>();
			buildSolutionFromVertexPath();

			long estimatedTime = System.currentTimeMillis() - startTime;

			//System.out.println("\nelapsed time "+ (double)(estimatedTime)/1000+" seconds");

		}else{
			solution = null;
			//System.out.println("Optimal Solution not computable! The problme is NP-Complete m8");
		}
	}

	//two vertex at position i and i+1 are such that abs(vertex(i),vertex(i+1))=1(left or right) or instance.size();(up and down)
	private void buildSolutionFromVertexPath() {
		List<Integer> pulite= new ArrayList<Integer>();

		int numsuck=0;
		for (int i = 0; i < completeSolutionPath.size()-1; i++) {
			int from=completeSolutionPath.get(i);
			int to=completeSolutionPath.get(i+1);
			int diff=from-to;
			if(targetCells.contains(from) && !pulite.contains(from) && bestPermutation.contains(from)){
				solution.add(new DynamicAction("suck"));
				pulite.add(from);
				numsuck++;
			}
			if(diff==1){//left
				solution.add(new DynamicAction("left"));
			}else if (diff==-1) {//right
				solution.add(new DynamicAction("right"));
			}else if (diff==instance.getSize()) {//up
				solution.add(new DynamicAction("up"));
			}else if (diff==-instance.getSize()) {//down
				solution.add(new DynamicAction("down"));

			}

		}//for
		if(instance.getBoardState()[instance.getBasePos().getX()][instance.getBasePos().getY()]==LocationState.Dirty){
			solution.add(new DynamicAction("suck"));
		}

		if(numsuck!= bestPermutation.size()-2){
			//System.out.println("qualcosa non vaaaaaa");
			//System.exit(-1);
		}
		solution.add(NoOpAction.NO_OP);

		//System.out.println("\nSOLUZIONE:");
		int count=1;
		for (Action soluAction : solution) {
			String name=((DynamicAction)soluAction).getName();
			//			System.out.print(name+" ");
			if(count%20==0)
				//System.out.println();
				count++;
		}
		//System.out.println();
	}

	private void isSolvable() {
		if(instance.getEnergy() < shortestDistance(RowMajIdx(instance.getAgentPos().getX(), instance.getAgentPos().getY(), instance.getSize()), RowMajIdx(instance.getBasePos().getX(), instance.getBasePos().getY(), instance.getSize())))

		{
			//System.out.println("Not Solvable");
			//System.out.println("EXITING");
			System.exit(-1);
		}

	}



	public void calculatePowerSet() {
		int n = targetCells.size()+1;
		for( long i = 0; i < (1 << n - 1); i++) {
			ArrayList<Integer> element = new ArrayList<Integer>();
			for( int j = 0; j < n; j++ )
				if( (i >> j) % 2 == 1 ) element.add(targetCells.get(j));
			powerSet.add(element); 
		}

		powerSet.remove(0);//l'insieme vuoto lo tolgo



	}






	public ArrayList<Integer> listAllreachableTarget() {
		ArrayList<Integer> target = new ArrayList<Integer>();
		for (int i = 0; i < instance.getSize(); i++) {
			for (int j = 0; j < instance.getSize(); j++) {
				if(instance.getBoardState()[i][j]==LocationState.Dirty){
					boolean unreachable = true;
					//controllo se reachABLE(almeno una distanza < MAX
					for (int k = 0; k < instance.getSize()&& unreachable; k++) {
						for (int l = 0; l < instance.getSize()&& unreachable; l++) {
							if(k!=i && l!=j){//non la stessa cella
								if(shortestDistance(RowMajIdx(i, j, instance.getSize()),RowMajIdx(k, l, instance.getSize())) < INFDIST	){
									unreachable=false;
								}
							}

						}
					}

					if(!unreachable){
						target.add(RowMajIdx(i, j, instance.getSize()));				
					}

				}

			}

		}


		return target;

	}
	//	public void calculateDistancesFloys(){
	//		int numVertices= instance.getSize()*instance.getSize();
	//		for (int k = 0; k < numVertices; k++) {
	//			for (int i = 0; i < numVertices; i++) {
	//				for (int j = 0; j < numVertices; j++) {
	//					distancesMatrix[i][j] = Math.min(distancesMatrix[i][j], distancesMatrix[i][k] + distancesMatrix[k][j]);
	//				}
	//
	//			}
	//
	//		}
	//	}



	public void calculateBestSolution(){
		for (List<Integer> listElement: powerSet ) {

			int minSizeCost=Integer.MAX_VALUE;
			boolean continua=true;
			////System.out.println("POWER SET : "+set+ "size "+listElement.size());
			for (List<Integer> perm: Collections2.orderedPermutations(listElement)) {
				int currCost=shortestDistance(RowMajIdx(instance.getAgentPos().getX(), instance.getAgentPos().getY(), instance.getSize()),perm.get(0));//dalla base al primo obiettivo
				currCost+=perm.size()*instance.getActionCosts().get("suck");//size suck operation devono essere effettuate
				for (int pathLoc=0;pathLoc <perm.size()-1;pathLoc++) {

					currCost+=shortestDistance(perm.get(pathLoc),perm.get(pathLoc+1));
					// TO-DO aggiungi il costo di suck e fai euristica qui 
				}
				currCost+=shortestDistance(perm.get(perm.size()-1),RowMajIdx(instance.getBasePos().getX(),instance.getBasePos().getY(), instance.getSize()));//dall'ultimo nodo dirty pulito alla base di nuovo

				if(currCost <= instance.getEnergy()){
					if( (currCost<minSizeCost || perm.size() > bestNumCleaned)){
						//abbiamo una nuova best solution
						bestNumCleaned=perm.size();
						bestPermutation.clear();
						bestPermutation.addAll(perm);
						bestCost=currCost;
						minSizeCost=currCost;
						//System.out.println("nuova soluzione migliore "+ bestPermutation + " con costo "+bestCost);
						if(bestPermutation.size()>= targetCells.size()){
							//System.exit(0);
						}
					}

				}



			}
		}

		//System.out.println("best perm "+ bestPermutation);
		//validation
		int cost =0;
		cost+=shortestDistance(RowMajIdx(instance.getAgentPos().getX(), instance.getAgentPos().getY(), instance.getSize()),bestPermutation.get(0));
		//System.out.println("costa "+cost+"arrivare dal pos al primo obiettivo");
		cost+=bestPermutation.size();
		for (int j = 0; j < bestPermutation.size()-1; j++) {
			cost+=shortestDistance(bestPermutation.get(j),bestPermutation.get(j+1));
		}
		cost+=shortestDistance(bestPermutation.get(bestPermutation.size()-1), RowMajIdx(instance.getBasePos().getX(),instance.getBasePos().getY(), instance.getSize()));
		if(cost==bestCost){
			//System.out.println("COSTTT VALIDATed  "+ cost);

		}




		if(bestPermutation.size()>0){
			if(!bestPermutation.get(0).equals(RowMajIdx(instance.getAgentPos().getX(), instance.getAgentPos().getY(), instance.getSize()))){
				bestPermutation.add(0, RowMajIdx(instance.getAgentPos().getX(), instance.getAgentPos().getY(), instance.getSize()));
			}
			if(!bestPermutation.get(bestPermutation.size()-1).equals(RowMajIdx(instance.getBasePos().getX(), instance.getBasePos().getY(), instance.getSize()))){
				bestPermutation.add(RowMajIdx(instance.getBasePos().getX(),instance.getBasePos().getY(), instance.getSize()));
			}


			//System.out.println("best path "+ bestPermutation + " con costo "+bestCost);

		}else{
			//System.out.println("\n\tNO SOLUTION");
		}


	}

	public List<Integer> buildCompletePath(){
		//System.out.println("BUILD COMPLETE PATH");
		List<Integer> completePath = new ArrayList<Integer>();
		DirectedGraph<Integer, DefaultEdge> directedGraph =
				new DefaultDirectedGraph<Integer, DefaultEdge>
		(DefaultEdge.class);


		for (int j = 0; j < instance.getSize()*instance.getSize(); j++) {
			directedGraph.addVertex(j);
		}

		for(int i=0;i<instance.getSize()*instance.getSize();i++){
			for (int j = 0; j < instance.getSize()*instance.getSize(); j++) {
				if(board.containsEdge(i, j)){
					directedGraph.addEdge(i,j);
					directedGraph.addEdge(j,i);
				}
			}
		}

		//System.out.println(bestPermutation+"best permutation");
		for (int pathLoc=0;pathLoc <bestPermutation.size()-1;pathLoc++) {

			List<DefaultEdge>tempStep;
			DijkstraShortestPath<Integer, DefaultEdge>pathFinder= new DijkstraShortestPath<Integer, DefaultEdge>(directedGraph,bestPermutation.get(pathLoc), bestPermutation.get(pathLoc+1));
			tempStep=pathFinder.getPathEdgeList();

			////System.out.println("bestpath between "+bestPermutation.get(pathLoc)+" and "+bestPermutation.get(pathLoc+1));
			for (DefaultEdge defaultEdge : tempStep) {


				if(completePath.size()==0 || !completePath.get(completePath.size()-1).equals((Integer) directedGraph.getEdgeSource(defaultEdge)) )
					completePath.add((Integer)directedGraph.getEdgeSource(defaultEdge));

				completePath.add((Integer) directedGraph.getEdgeTarget(defaultEdge));

				//System.out.print((Integer)directedGraph.getEdgeSource(defaultEdge)+" "+(Integer) directedGraph.getEdgeTarget(defaultEdge)+" " );


			}
			//			//System.out.println();

		}


		//System.out.println("COMPLETE PATH:");

		//		for (Integer integer : completePath) {
		//			System.out.print(" "+integer);	
		//		}
		return completePath;
	}





	private int RowMajIdx(int x, int y, int size){
		return x*size+y;
	}
	private UndirectedGraph<Integer, DefaultEdge> createGraph()
	{
		UndirectedGraph<Integer, DefaultEdge> g =
				new SimpleGraph<Integer, DefaultEdge>(DefaultEdge.class);

		for (int i = 0; i <instance.getSize() ; i++) {
			for (int j = 0; j < instance.getSize(); j++) {
				g.addVertex(new Integer(RowMajIdx(i, j, instance.getSize())));

			}			
		}

		//rendo le celle ostacolo irraggiungibili. nessuna connnessione in uscita ne in entrata
		//escludo gli angoli. Quando da una cella dentro il bordo creo un arco automaticamente creo l'arco opposto
		for (int i = 0; i <instance.getSize() ; i++) {
			for (int j = 0; j < instance.getSize(); j++) {
				//celle dentro il bordo esterno
				if(instance.getBoardState()[i][j]!=LocationState.Obstacle){
					if(i>0 && i<instance.getSize()-1){
						if(j>0 && j<instance.getSize()-1){
							if(instance.getBoardState()[i-1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i-1, j, instance.getSize()));
							}

							if(instance.getBoardState()[i+1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i+1, j, instance.getSize()));
							}

							if(instance.getBoardState()[i][j+1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j+1, instance.getSize()));
							}

							if(instance.getBoardState()[i][j-1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j-1, instance.getSize()));
							}
						}
					}

					//prima riga senza angoli
					if(i==0){
						if(j>0 && j<instance.getSize()-1){
							if(instance.getBoardState()[i+1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i+1, j, instance.getSize()));
							}

							if(instance.getBoardState()[i][j+1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j+1, instance.getSize()));
							}

							if(instance.getBoardState()[i][j-1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j-1, instance.getSize()));
							}
						}
					}

					//ultimariga senza angoli
					if(i==instance.getSize()-1){
						if(j>0 && j<instance.getSize()-1){
							if(instance.getBoardState()[i-1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i-1, j, instance.getSize()));
							}


							if(instance.getBoardState()[i][j+1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j+1, instance.getSize()));
							}

							if(instance.getBoardState()[i][j-1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j-1, instance.getSize()));
							}
						}
					}


					//prima colonna senza angoli
					if(j==0){
						if(i>0 && i<instance.getSize()-1){
							if(instance.getBoardState()[i-1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i-1, j, instance.getSize()));
							}

							if(instance.getBoardState()[i+1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i+1, j, instance.getSize()));
							}

							if(instance.getBoardState()[i][j+1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j+1, instance.getSize()));
							}


						}
					}

					//ultima colonna senza angoli
					if(j==instance.getSize()-1){
						if(i>0 && i<instance.getSize()-1){
							if(instance.getBoardState()[i-1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i-1, j, instance.getSize()));
							}

							if(instance.getBoardState()[i+1][j]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i+1, j, instance.getSize()));
							}


							if(instance.getBoardState()[i][j-1]!=LocationState.Obstacle){
								g.addEdge(RowMajIdx(i, j, instance.getSize()), RowMajIdx(i, j-1, instance.getSize()));
							}


						}
					}


				}//obstacle
			}			//forj
		}//fori


		return g;
	}


	public static void main(String[] args) {
		Vacuum_Agent_Solver agent = new Vacuum_Agent_Solver();
		agent.solve("brutta1.xml");
	}




	public List<Action> getSolution() {
		return solution;
	}


	public void setSolution(List<Action> solution) {
		this.solution = solution;
	}


	@Override
	public void run() {
		this.solve();

	}

}
